package com.zk;

import java.io.PrintWriter;
import java.util.ArrayList;
import java.util.List;
import java.util.Scanner;

/**
 * https://blog.csdn.net/xuchishao/article/details/49231119
 */
public class FindMedian implements AlgoInteraction {

    /**
     * 查找中位数
     *
     * @param array
     * @return
     */
    public int find(int[] array) {
        if (array.length % 2 == 1) {
            return findMedian(array, (array.length + 1) / 2, 0, array.length - 1);
        } else {
            return findMedian(array, array.length / 2, 0, array.length - 1);
        }
    }

    private void swap(int[] a, int i, int j) {
        int temp = a[i];
        a[i] = a[j];
        a[j] = temp;
    }

    private int partition(int[] arr, int low, int high) {
        int pivot = arr[low];
        int i = low, j = high;

        while (i <= j) {
            while (i <= j && arr[i] <= pivot) i++;
            while (i <= j && arr[j] >= pivot) j--;
            swap(arr, i, j);
        }

        swap(arr, low, j);
        return j;
    }

    //第k大的数，如果数组长度奇数，则k=(1+n)/2, 否则k=n/2
    private int findMedian(int[] arr, int k, int low, int high) {
        if (k > high - low + 1)
            return -1;

        int pos = partition(arr, low, high);
        if (pos - low < k - 1) {
            return findMedian(arr, k - pos - 1, pos + 1, high);
        } else if (pos - low == k - 1) {
            return arr[pos];
        } else {
            return findMedian(arr, k, low, pos - 1);
        }
    }

    public void exec(Scanner scanner, PrintWriter printWriter) {
        printWriter.println("请输入整数,每行一个(-1 表示结束输入):");

        List<Integer> integerList = new ArrayList<>(8);
        int curInt = -1;
        while ((curInt = scanner.nextInt()) != -1) {
            integerList.add(curInt);
        }

        printWriter.println("您输入的整数数组为:" + integerList);

        int[] array = integerList.stream().mapToInt(Integer::intValue).toArray();
        int median = find(array);

        printWriter.println("中位数为:" + median);
    }
}
